iT邦幫忙

2024 iThome 鐵人賽

DAY 14
0

題目

Leetcode 2024/09/14 Daily
2419. Longest Subarray With Maximum Bitwise AND
難度: 中等偏易

題意

給定一整數陣列nums,求最長的子陣列的長度,使得所有子陣列元素AND值最大。

方向

Naive法: 用雙指標(Two pointer)造出所有的子陣列,再一個個把元素AND起來;複雜度為O(N^3)。

觀察題目給的輸入限制,輸入的長度為10^5。
根據經驗,五次方的輸入要在O(N)時間內做完才能AC。

再觀察題目給的範例,發現使子陣列元素AND值最大,其實就是子陣列的元素都必須是原陣列的最大值
因為AND的特性,兩數互相AND,BIT為1的數量只能越來越少,其值也會越來越小。
也就是A & B <= min(A, B)

因此此題先first pass,求出最大值;再second pass求出元素皆為最大值的最長子陣列。

實作

class Solution
{
public:
    int longestSubarray(vector<int> &nums)
    {
        int n = (int)nums.size();
        int maximum = *max_element(nums.begin(), nums.end());

        int res = 0;   // Size of subarray
        int left = -1; // Last begin index of consecutive maximum subarray
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == maximum && left == -1)
                left = i;
            else if (nums[i] != maximum && left != -1)
            {
                res = max(res, i - left);
                left = -1;
            }
        }
        if (left != -1)
            res = max(res, n - left);

        return res;
    }
};

分析

時間複雜度: O(N),two pass
空間複雜度: O(1)

結果

Time Submitted Status Runtime Memory Language
09/14/2024 14:56 Accepted 104 ms 84.9 MB cpp

上一篇
[9/13] 區間異或
下一篇
[9/15] 最長子陣列中母音偶數個
系列文
菜就多練,不會就多刷31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言